{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Betweenness Centrality\n",
    "\n",
    "In this notebook, we will compute the Betweenness centrality of each vertex in our test datase using both cuGraph and NetworkX. The NetworkX and cuGraph processes will be interleaved so that each step can be compared.\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees\n",
    "* Created:   04/24/2019\n",
    "* Last Edit: 04/24/2020\n",
    "\n",
    "RAPIDS Versions: 0.14   \n",
    "\n",
    "Test Hardware\n",
    "\n",
    "* GV100 32G, CUDA 10.2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "Betweenness centrality is a measure of the relative importance of a vertex within the graph based on measuring the number of shortest paths that pass through each vertex.  High betweenness centrality vertices have a greater number of path cross over the vertex.  \n",
    "\n",
    "See [Betweenness on Wikipedia](https://en.wikipedia.org/wiki/Betweenness_centrality) for more details on the algorithm.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Betweenness centrality of a node 𝑣 is the sum of the fraction of all-pairs shortest paths that pass through 𝑣\n",
    "\n",
    "<img src=\"https://latex.codecogs.com/png.latex?c_B(v)&space;=\\sum_{s,t&space;\\in&space;V}&space;\\frac{\\sigma(s,&space;t|v)}{\\sigma(s,&space;t)}\" title=\"c_B(v) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|v)}{\\sigma(s, t)}\" />\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To compute the Betweenness centrality scores for a graph in cuGraph we use:<br>\n",
    "__df = cugraph.betweenness_centrality(G)__\n",
    "\n",
    "    G: cugraph.Graph object\n",
    "   \n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: a cudf.DataFrame object with two columns:\n",
    "        df['vertex']: The vertex identifier for the vertex\n",
    "        df['betweenness_centrality']: The betweenness centrality score for the vertex\n",
    "\n",
    "\n",
    "\n",
    "### _NOTICE_\n",
    "cuGraph does not currently support the ‘endpoints’ and ‘weight’ parameters as seen in the corresponding networkX call. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be of any data type and do not need to be contiguous. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n",
    "\n",
    "\n",
    "The test data has vertex IDs strating at 1.  We will be using the auto-renumber feature of cuGraph to renumber the data so that the starting vertex ID is zero.  The data will be auto-unrenumbered so that the renumbering step is transparent to users. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NetworkX libraries\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the path to the test data  \n",
    "datafile='../data/karate-data.csv'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read in the data - GPU\n",
    "cuGraph depends on cuDF for data loading and the initial Dataframe creation\n",
    "\n",
    "The data file contains an edge list, which represents the connection of a vertex to another.  The `source` to `destination` pairs is in what is known as Coordinate Format (COO).  In this test case, the data is just two columns.  However a third, `weight`, column is also possible"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gdf = cudf.read_csv(datafile, delimiter='\\t', names=['src', 'dst'], dtype=['int32', 'int32'] )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph using the source (src) and destination (dst) vertex pairs from the Dataframe \n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Call the Betweenness Centrality algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.betweenness_centrality \n",
    "gdf_bc = cugraph.betweenness_centrality(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_It was that easy!_  \n",
    "\n",
    "----\n",
    "\n",
    "Let's now look at the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Find the most important vertex using the scores\n",
    "# This methods should only be used for small graph\n",
    "def find_top_scores(_df) :\n",
    "    m = _df['betweenness_centrality'].max()\n",
    "    return _df.query('betweenness_centrality >= @m')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top_df = find_top_scores(gdf_bc)\n",
    "top_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's sort the data and look at the top 5 vertices\n",
    "gdf_bc.sort_values(by='betweenness_centrality', ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now compute using NetworkX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read the data, this also created a NetworkX Graph \n",
    "file = open(datafile, 'rb')\n",
    "Gnx = nx.read_edgelist(file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx = nx.betweenness_centrality(Gnx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx_s = sorted(((value, key) for (key,value) in bc_nx.items()), reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc_nx_s[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned, the scores are different but the ranking is the same."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019-2020, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cugraph_dev",
   "language": "python",
   "name": "cugraph_dev"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
